/********************************************************************
	Created:	2012/06/08  22:24
	Filename: 	RLib_HashMap.cpp
	Author:		rrrfff
	Url:	    http://blog.csdn.net/rrrfff
*********************************************************************/
#include "RLib_HashMap.h"
using namespace System::Collections::Generic;
//-------------------------------------------------------------------------


HashMap::HashMap()
{
    allocator_ = NULL;
    match_ = NULL;
}

//-------------------------------------------------------------------------


HashMap::HashMap(Comparable<void>::IComparable match, Allocator *allocator /* = &PublicDefaultAllocator */, unsigned int initial_capacity /* = 8 */)
{
    allocator_ = allocator;
    match_ = match;
    Initialize(initial_capacity);
}

//-------------------------------------------------------------------------


HashMap::~HashMap()
{
    if (allocator_)
    {
        allocator_->Free(map_);
    }
}

//-------------------------------------------------------------------------


HashMap::Entry *HashMap::Lookup(void *key, uint32_t hash, bool insert)
{
    // Find a matching entry.
    Entry *p = Probe(key, hash);
    if (p->key != nullptr)
    {
        return p;
    }

    // No entry found; insert one if necessary.
    if (insert)
    {
        p->key = key;
        p->value = NULL;
        p->hash = hash;
        occupancy_++;

        // Grow the map if we reached >= 80% occupancy.
        if (occupancy_ + occupancy_ / 4 >= capacity_)
        {
            Resize();
            p = Probe(key, hash);
        }

        return p;
    }

    // No entry found and none inserted.
    return NULL;
}

//-------------------------------------------------------------------------


void HashMap::Remove(void *key, uint32_t hash)
{
    // Lookup the entry for the key to remove.
    Entry *p = Probe(key, hash);
    if (p->key == nullptr)
    {
        // Key not found nothing to remove.
        return ;
    }

    // To remove an entry we need to ensure that it does not create an empty
    // entry that will cause the search for another entry to stop too soon. If all
    // the entries between the entry to remove and the next empty slot have their
    // initial position inside this interval, clearing the entry to remove will
    // not break the search. If, while searching for the next empty entry, an
    // entry is encountered which does not have its initial position between the
    // entry to remove and the position looked at, then this entry can be moved to
    // the place of the entry to remove without breaking the search for it. The
    // entry made vacant by this move is now the entry to remove and the process
    // starts over.
    // Algorithm from http://en.wikipedia.org/wiki/Open_addressing.

    // This guarantees loop termination as there is at least one empty entry so
    // eventually the removed entry will have an empty entry after it.
    ASSERT(occupancy_ < capacity_);

    // p is the candidate entry to clear. q is used to scan forwards.
    Entry *q = p; // Start at the entry to remove.
    while (true)
    {
        // Move q to the next entry.
        q = q + 1;
        if (q == map_end())
        {
            q = map_;
        }

        // All entries between p and q have their initial position between p and q
        // and the entry p can be cleared without breaking the search for these
        // entries.
        if (q->key == nullptr)
        {
            break;
        }

        // Find the initial position for the entry at position q.
        Entry *r = map_ + (q->hash &(capacity_ - 1));

        // If the entry at position q has its initial position outside the range
        // between p and q it can be moved forward to position p and will still be
        // found. There is now a new candidate entry for clearing.
        if ((q > p && (r <= p || r > q)) || (q < p && (r <= p && r > q)))
        {
            *p =  *q;
            p = q;
        }
    }

    // Clear the entry which is allowed to en emptied.
    p->key = NULL;
    occupancy_--;
}

//-------------------------------------------------------------------------


void HashMap::Clear()
{
    // Mark all entries as empty.
    const Entry *end = map_end();
    for (Entry *p = map_; p < end; p++)
    {
        p->key = NULL;
    }
    occupancy_ = 0;
}

//-------------------------------------------------------------------------


HashMap::Entry *HashMap::Start()const
{
    return Next(map_ - 1);
}

//-------------------------------------------------------------------------


HashMap::Entry *HashMap::Next(Entry *p)const
{
    const Entry *end = map_end();
    ASSERT(map_ - 1 <= p && p < end);
    for (p++; p < end; p++)
    {
        if (p->key != nullptr)
        {
            return p;
        }
    }
    return NULL;
}

//-------------------------------------------------------------------------


HashMap::Entry *HashMap::Probe(void *key, uint32_t hash)
{
    ASSERT(key != nullptr);

    Entry *p = map_ + (hash &(capacity_ - 1));
    const Entry *end = map_end();
    ASSERT(map_ <= p && p < end);

    ASSERT(occupancy_ < capacity_); // Guarantees loop termination.
    while (p->key != nullptr && (hash != p->hash || !match_(key, p->key)))
    {
        p++;
        if (p >= end)
        {
            p = map_;
        }
    }

    return p;
}

//-------------------------------------------------------------------------


void HashMap::Initialize(uint32_t capacity)
{
    map_ = reinterpret_cast < Entry * > (allocator_->Alloc(capacity *sizeof(Entry)));
    if (map_ == nullptr)
    {
        assert(!"FatalProcessOutOfMemory(HashMap::Initialize)");
        return ;
    }
    capacity_ = capacity;
    Clear();
}

//-------------------------------------------------------------------------


void HashMap::Resize()
{
    Entry *map = map_;
    uint32_t n = occupancy_;

    // Allocate larger map.
    Initialize(capacity_ *2);

    // Rehash all current entries.
    for (Entry *p = map; n > 0; p++)
    {
        if (p->key != nullptr)
        {
            Lookup(p->key, p->hash, true)->value = p->value;
            n--;
        }
    }

    // Free old map.
    allocator_->Free(map);
}
